import java.util.Arrays;

public class Merge {
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 9, 1, 5, 7, 4, 10, 44, 45, 1, 2, 3};
        mergesort(arr, 0, arr.length - 1);
        System.out.println("排序结果: " + Arrays.toString(arr));
    }

    public static void merge(int[] arr, int left, int mid, int right) {

        int[] arr1 = new int[mid - left + 1];
        for (int k = 0; k < arr1.length; k++) {
            arr1[k] = arr[left + k];
        }
        int i = 0;
        int j = mid + 1;
        for (int k = left; k <= right; k++) {
            if (i > arr1.length - 1) {
                arr[k] = arr[j++];
            } else if (j > right) {
                arr[k] = arr1[i++];
            } else if (arr1[i] > arr[j])
                arr[k] = arr[j++];
            else if (arr1[i] <= arr[j]) {
                arr[k] = arr1[i++];
            }
        }
    }

    public static void mergesort(int[] arr, int left, int right) {
        if (left >= right)
            return;
        int mid = (left + right) / 2;
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
